Field of the Invention
The present invention relates to ordered list management and more particularly to ordered list management in a replicated environment.
Description of the Related Art
In mathematics, an ordered list is a sequence of elements arranged in a particular order. The concept of an ordered list forms an integral component of computing in that the establishment and maintenance of an ordered list enjoys wide application across many different types of computer programs. Maintaining an ordered list in a single user application involves nothing more than programmatically establishing a data structure in memory to accommodate an ordered list of a particular size and populating the data structure with the requisite elements in a specified order. To that end, an ordered list can be represented by an array, a database table, or a linked list to name a few possible rudimentary structures.
While managing an ordered list in a single user application can be of little consequence, managing an ordered list in a multi-user environment can be challenging. In this regard, in a multi-user environment, peer users can access a single ordered list and add, delete, modify or re-order one or more elements in the ordered list. In the circumstance where each peer user applies changes to the ordered list in sequence, the changes can be applied incrementally so that no conflicts result. However, if peer users apply changes to an ordered list in parallel, conflicts can result. In a client-server environment, managing conflicts amongst changes to an ordered list by different users can be simple to the extent that the changes are managed at the server acting as a gatekeeper to the ordered list. Not so in a peer-to-peer environment.
U.S. Pat. No. 7,603,362 to Geoffrey John Elliot et al. for ORDERED LIST MANAGEMENT addresses the issue of peer to peer management of an ordered list. In the Elliot patent, it is recognized that peer-to-peer file sharing networks—particularly as they relate to the sharing of music play lists—facilitate conflicts resulting from the parallel modification of a play list. As suggested in the Elliot patent, a globally unique identifier is appended to the path value of a position of an item in an ordered list to enable simultaneous or near simultaneous modifications to the ordered list without conflict. Further, an ordered list-specific seed value may be pre-pended to the path value of each item value to ensure clustering of ordered list items when two or more ordered lists are merged.
Like a peer-to-peer computing environment, in a replication environment ordered lists can be modified or merged in parallel by different peer users. Replication refers to the copying of data in two different computing systems and the synchronization of the data so that one replicated set of data is a mirror image of another from which the replicated set of data had been created. Thus, in a replication environment, one user can edit an ordered list locally by changing an ordering of the list while another user can edit the same ordered list also locally. During replication, the changes by each end user must be reconciled before merging the replicated ordered list into a single ordered list. Further, to the extent that different users modify items in a list separately in a replication environment, the ordering algorithms for the ordered list execute separately resulting in duplicate ordering numbers, mixing of items created by multiple users and generally unpredictable ordering of the merged form of the ordered lists.